package com.formula.datastructure.exercise.tree;

/**
 * 记得画图
 */
public class AVLNode {

    public Integer data;

    public AVLNode left;

    public AVLNode right;

    public AVLNode(Integer data) {
        this.data = data;
    }

    // 自己的高度
    private int getHeight() {
        int leftHeight = 0;
        int rightHeight = 0;
        if (left != null) {
            leftHeight = left.getHeight();
        }
        if (right != null) {
            rightHeight = right.getHeight();
        }
        return 1 + leftHeight > rightHeight ? leftHeight : rightHeight;
    }

    // 左子树高度, 递归是倒着来的，第一个发现左右高度不对是parent
    public int getLeftHeight() {
        return left == null ? 0 : left.getHeight();
    }

    // 这是拿右子树的高度, 不是自己的高度
    public int getRightHeight() {
        return right == null ? 0 : right.getHeight();
    }

    public void addChild(AVLNode newNode) {
        addChild(newNode, this);
    }

    /**
     * 先插入，再调整
     *
     * @param newNode
     */
    private void addChild(AVLNode newNode, AVLNode grandPa) {
        if (newNode.data.equals(data)) {
            System.out.println("has existed.");
        } else if (newNode.data > data) {
            if (right == null) {
                right = newNode;
            } else {
                right.addChild(newNode, right);
            }
        } else {
            if (left == null) {
                left = newNode;
            } else {
                left.addChild(newNode, left);
            }
        }
        /**
         * 逻辑: 新加导致失衡一定产生了是祖孙三代
         * 记 parent为失衡, child为parent唯一的孩子
         * 左左失衡，父右
         * 左右失衡，子左父右
         * 右右失衡，父左
         * 右左失衡，子右父左
         *
         * 左旋:
         * 右旋:
         */

        // 递归是倒着来的, 第一个发现左右不等是parent
        if (getLeftHeight() - getRightHeight() == 2) {
            //左边高, 肯定有左子树
            AVLNode child = left;

            if (child.left != null) {
                // 左左, 父右
                grandPa.left = child;
                child.right = this;
                this.left = null;
            } else if (child.right != null) {
                // 左右, 子左父右
                AVLNode grandChild = child.right;
                left = grandChild;
                grandChild.left = child;
                child.right = null;
                // 左左, 父右
                this.left = child;
                child.right = this;
                this.left = null;
            }
        }
        if (getRightHeight() - getLeftHeight() == 2) {
            AVLNode child = this.right;
            if (child.right != null) {
                // 右右
                right = child;
                child.left = this;
                this.right = null;
            } else if (child.left != null) {
                // 右左
                AVLNode grandChild = child.left;
                this.right = grandChild;
                grandChild.right = child;
                child.left = null;
                // 右右
                right = child;
                child.left = this;
                this.right = null;
            }
        }
    }
}
